package com.zyk.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/4/3 15:22
 */
public class J57 {

    /** https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/ */
    public static int[] twoSum(int[] nums, int target) {
        // 有序数组, 求两个数正好为target, 二分
        int l = 0, r = nums.length-1;
        int[] ans = new int[2];
        while (l < r) {
            if(nums[l] + nums[r] == target) {
                ans[0] = nums[l];
                ans[1] = nums[r];
                break;
            }else if(nums[l] + nums[r] < target) {
                l++;
            }else {
                r--;
            }
        }
        return ans;
    }

    /** https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/ */
    // 暴力解
    public static int[][] findContinuousSequence(int target) {
        // 从1开始算
        List<int[]> ans = new ArrayList<>();

        for (int i = 1; i < target; i++) {
            int sum = 0;
            for (int j = i; j < target; j++) {
                sum += j;
                if(sum > target) {
                    sum = 0;
                    break;
                }else if(sum == target) {
                    int[] res = new int[j-i+1];
                    for (int k = i; k <= j; k++) {
                        res[k-i] = k;
                    }
                    ans.add(res);
                    sum = 0;
                    break;
                }
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }


    // for test
    public static boolean isEqual(int[][] a, int[][] b) {
        if(a.length != b.length) {
            return false;
        }
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if(a[i][j] != b[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    // for test
    public static void main(String[] args) {
        for (int i = 1; i <= 1000; i++) {
            int[][] ans1 = findContinuousSequence(i);
        }
    }

}
